package leetcode.weekly.week307;

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {

	public long kSum(int[] nums, int k) {
		long sum = 0;
		for (int i = 0; i < nums.length; i++) {
			sum += Math.max(0, nums[i]);
			nums[i] = Math.abs(nums[i]);//---
		}
		if (k == 1) {
			return sum;
		}
		Arrays.sort(nums);
		PriorityQueue<long[]> queue = new PriorityQueue<>((o, p) -> Long.compare(p[0], o[0]));
		queue.offer(new long[] { sum - nums[0], 0 });
		for (int i = 2; i < k; i++) {
			long[] poll = queue.poll();
//			if (poll[1] < nums.length - 1) {
				long next = poll[1] + 1;
				queue.offer(new long[] { poll[0] + nums[(int) poll[1]] - nums[(int) next], next });
				queue.offer(new long[] { poll[0] - nums[(int) next], next });
//			}
		}
		return queue.peek()[0];
	}
}